/*
*
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：

输入：matrix = [[1]]
输出：1

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

  - @author ala
  - @date 2024-09-20 16:28
*/
package main

import (
	"container/heap"
	_ "container/heap"
	"fmt"
)

func main() {
	//matrix := [][]int{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}
	matrix := [][]int{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}
	//matrix := [][]int{{1}}

	fmt.Println(longestIncreasingPath(matrix))
}

/**
 *	1）dp[i][j]表示：(i,j)点的最长路径数
 *	2）从最小的元素开始，如果他的上下左右存在比他小的元素，则：
 *		dp[i][j] = max(dp[_i][_j]) + 1
 *		其中：(_i, _j)是他的上下左右存在比他小的元素
 */
func longestIncreasingPath(matrix [][]int) int {
	//return V1(matrix)
	return V2(matrix)
}

var POINTS = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

var _matrix *[][]int

/**
 *	1）堆维护从小到大遍历
 */
func V1(matrix [][]int) int {
	_matrix = &matrix
	M, N := len(matrix), len(matrix[0])
	pq := PQ{}
	for i := range matrix {
		for j := range matrix[i] {
			heap.Push(&pq, []int{i, j})
		}
	}
	dp := make([][]int, M)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	mx := 0
	for !(len(pq) == 0) {
		p := heap.Pop(&pq).([]int)
		i, j := p[0], p[1]
		_mx := 0
		for _, p := range POINTS {
			_i, _j := i+p[0], j+p[1]
			if _i < 0 || _i == M || _j < 0 || _j == N || matrix[i][j] <= matrix[_i][_j] {
				continue
			}
			_mx = max(_mx, dp[_i][_j])
		}
		dp[i][j] = _mx + 1
		mx = max(mx, dp[i][j])
	}
	return mx
}

type PQ [][]int

func (pq *PQ) Len() int { return len(*pq) }
func (pq *PQ) Less(i, j int) bool {
	v1, v2 := (*_matrix)[(*pq)[i][0]][(*pq)[i][1]], (*_matrix)[(*pq)[j][0]][(*pq)[j][1]]
	return v1 < v2
}
func (pq *PQ) Swap(i, j int) {
	(*pq)[i][0], (*pq)[i][1], (*pq)[j][0], (*pq)[j][1] = (*pq)[j][0], (*pq)[j][1], (*pq)[i][0], (*pq)[i][1]
}
func (pq *PQ) Push(x any) {
	*pq = append(*pq, x.([]int))
}
func (pq *PQ) Pop() any {
	n := len(*pq)
	last := (*pq)[n-1]
	(*pq)[n-1] = nil
	*pq = (*pq)[0 : n-1]
	return last
}

/**
 *	1）拓补序的方式优化掉堆
 *		先好到入度为0的点，作为开始点
 *	2）dp[i][j]表示可以走到(i,j)点的最长路径
 *		如果(i,j)周围的点比他小，则dp[i][j] = max(dp[_i][_j] + 1)
 *		如果(i,j)周围的点比他大，则dp[_i][_j]的入度-1
 *	3）把入度减到0的点继续遍历，直到没有入度为0的点
 */
func V2(matrix [][]int) int {
	M, N := len(matrix), len(matrix[0])

	//	入度为0的点
	queue := make([][]int, M*N)
	ql, qr, qs := 0, -1, 0
	//	入度统计
	ins := make([][]int, M)
	for i := range ins {
		ins[i] = make([]int, N)
	}
	for i := range matrix {
		for j := range matrix[i] {
			for _, p := range POINTS {
				_i, _j := i+p[0], j+p[1]
				if _i < 0 || _i == M || _j < 0 || _j == N || matrix[_i][_j] >= matrix[i][j] {
					continue
				}
				ins[i][j]++
			}
			if ins[i][j] == 0 {
				qr, qs = qr+1, qs+1
				queue[qr] = []int{i, j}
			}
		}
	}

	dp := make([][]int, M)
	for i := range dp {
		dp[i] = make([]int, N)
	}
	//	从入度为0的点开始，计算dp
	mx := 0
	for qs > 0 {
		rs := queue[ql : qr+1]
		qs -= qr - ql + 1
		ql = qr + 1
		for _, r := range rs {
			i, j, v, _mx := r[0], r[1], matrix[r[0]][r[1]], 0
			for _, p := range POINTS {
				_i, _j := i+p[0], j+p[1]
				if _i < 0 || _i == M || _j < 0 || _j == N {
					continue
				}
				_v := matrix[_i][_j]

				if v < _v {
					ins[_i][_j]--
					if ins[_i][_j] == 0 {
						qr++
						queue[qr] = []int{_i, _j}
						qs++
					}
				}
				if v > _v {
					_mx = max(_mx, dp[_i][_j])
				}
			}
			dp[i][j] = _mx + 1
			mx = max(mx, dp[i][j])
		}
	}
	return mx
}
